{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Chunks To Make Sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxChunksToSorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多能完成排序的块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的整数数组 <code>arr</code> ，它表示在 <code>[0, n - 1]</code> 范围内的整数的排列。</p>\n",
    "\n",
    "<p>我们将 <code>arr</code> 分割成若干 <strong>块</strong> (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。</p>\n",
    "\n",
    "<p>返回数组能分成的最多块数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> arr = [4,3,2,1,0]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong>\n",
    "将数组分成2块或者更多块，都无法得到所需的结果。\n",
    "例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> arr = [1,0,2,3,4]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong>\n",
    "我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。\n",
    "然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。\n",
    "对每个块单独排序后，结果为 [0, 1], [2], [3], [4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == arr.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt; n</code></li>\n",
    "\t<li><code>arr</code>&nbsp;中每个元素都 <strong>不同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-chunks-to-make-sorted](https://leetcode.cn/problems/max-chunks-to-make-sorted/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-chunks-to-make-sorted](https://leetcode.cn/problems/max-chunks-to-make-sorted/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,1,0]', '[1,0,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack_max = []\n",
    "        \n",
    "        for v in arr:                       \n",
    "            if stack_max!=[] and v<stack_max[-1]:\n",
    "                head = stack_max[-1] # max at the moment\n",
    "                while stack_max and v<stack_max[-1]: \n",
    "                    stack_max.pop() \n",
    "                    #if current element < stack peek (previous max, each max represent a block), then merge into a single block\n",
    "                stack_max.append(head) # append the max of the newly merged block\n",
    "            else:\n",
    "                stack_max.append(v)\n",
    "                \n",
    "        return len(stack_max)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: 'List[int]') -> 'int':\n",
    "        l = sorted(arr)\n",
    "        count = 0\n",
    "        sum1, sum2 = 0, 0\n",
    "        for i in range(len(arr)):\n",
    "            sum1 += arr[i]\n",
    "            sum2 += l[i]\n",
    "            if sum1 == sum2 :\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        stack = []\n",
    "        n = arr[0]\n",
    "        for num in arr:\n",
    "            if num > n:\n",
    "                stack.append(num)\n",
    "                n = num\n",
    "            else:\n",
    "                stack.append(n)\n",
    "\n",
    "        n = arr[-1]\n",
    "        stack1 = []\n",
    "        for num in reversed(arr):\n",
    "            if num < n:\n",
    "                stack1.insert(0,num)\n",
    "                n = num\n",
    "            else:\n",
    "                stack1.insert(0,n)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(len(arr)-1):\n",
    "            if stack[i] <= stack1[i+1]:\n",
    "                ans += 1\n",
    "        # print(stack)\n",
    "        # print(stack1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        for a, b in zip(arr, sorted(arr)):\n",
    "            sum1 += a\n",
    "            sum2 += b\n",
    "            res += sum1 == sum2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        counter1 = collections.Counter()\n",
    "        counter2 = collections.Counter()\n",
    "        for a, b in zip(arr, sorted(arr)):\n",
    "            counter1[a] += 1\n",
    "            counter2[b] += 1\n",
    "            res += counter1 == counter2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        newarr = sorted(arr)\n",
    "        sarr = snewarr = pieces = 0\n",
    "        \n",
    "        for i in range(len(newarr)):\n",
    "            sarr += arr[i]\n",
    "            snewarr += newarr[i]\n",
    "            if sarr - snewarr == 0:\n",
    "                pieces += 1\n",
    "                sarr = snewarr =0\n",
    "        return pieces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    # def heapremove(self,heap,val):\n",
    "\n",
    "    def maxChunksToSorted(self, arr) -> int:\n",
    "        #找出最短的块，使得这一块的数字小于等于后面所有数字\n",
    "        #这一块的数字中最大数字比后面所有数字中最小的数字还要小(或等于)\n",
    "        #这一块用大顶堆表示，后一块用小顶堆表示，还得实现小顶堆的remove操作\n",
    "        if not arr:\n",
    "            return 0\n",
    "        res=0\n",
    "        i=0 #right最左边元素下标\n",
    "        left=[]\n",
    "        right=arr[:]\n",
    "        heapq.heapify(left)\n",
    "        heapq.heapify(right)\n",
    "        while right:\n",
    "            if not left:\n",
    "                left.append(-arr[i])\n",
    "                right=arr[i+1:]\n",
    "                heapq.heapify(right)\n",
    "                i+=1\n",
    "                res+=1\n",
    "            elif -left[0]>right[0]:\n",
    "                right=arr[i+1:]\n",
    "                heapq.heapify(right)\n",
    "                heapq.heappush(left,-arr[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                # res+=1\n",
    "                left=[]\n",
    "        return res\n",
    "# fuck=Solution()\n",
    "# print(fuck.maxChunksToSorted([2,1,3,4,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        count = collections.defaultdict(int)\n",
    "        ans = nonzero = 0\n",
    "\n",
    "        for x, y in zip(arr, sorted(arr)):\n",
    "            count[x] += 1\n",
    "            if count[x] == 0: nonzero -= 1\n",
    "            if count[x] == 1: nonzero += 1\n",
    "\n",
    "            count[y] -= 1\n",
    "            if count[y] == -1: nonzero += 1\n",
    "            if count[y] == 0: nonzero -= 1\n",
    "\n",
    "            if nonzero == 0: ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if stack and num<stack[-1]:\n",
    "                head = stack.pop()\n",
    "                while stack and num<stack[-1]:\n",
    "                    stack.pop()\n",
    "                stack.append(head)\n",
    "            else:\n",
    "                stack.append(num)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# O(N)\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        \n",
    "        left_max = [arr[0]]\n",
    "        for num in arr[1:]:\n",
    "            left_max = left_max + [max(left_max[-1], num)]\n",
    "\n",
    "        right_min = [arr[-1]]\n",
    "        for num in arr[::-1][1:]:\n",
    "            right_min = [min(right_min[0], num)] + right_min\n",
    "\n",
    "\n",
    "        return 1 + sum([int(right_min[i+1]>=left_max[i]) for i in range(len(arr)-1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        res = 0\n",
    "        cur_max = float('-inf')\n",
    "        for i in range(len(arr) - 1):\n",
    "            cur_max = max(cur_max, arr[i])\n",
    "            if cur_max <= min(arr[i + 1:]):\n",
    "                res += 1\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack=[]\n",
    "        for a in range(len(arr)):\n",
    "            if not stack or arr[a]>=arr[stack[-1]]:\n",
    "                stack.append(a)\n",
    "            else:\n",
    "                while len(stack)>=2 and arr[stack[-2]]>arr[a]:\n",
    "                        stack.pop(-2)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # 769题可以使用索引，即找绝对位置\n",
    "        # 本题只有相对大小，可以通过排序取相对位置，转化为[0,n-1]的区间\n",
    "        arr=sorted(enumerate(arr),key=lambda x:x[1])\n",
    "        idxs,_=zip(*arr)\n",
    "        res,m=0,-1\n",
    "        for i in range(len(idxs)):\n",
    "            m=max(m,idxs[i])\n",
    "            if m==i:res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "    \n",
    "        def split(start,end):\n",
    "            count=0\n",
    "            for i in range(start,end):\n",
    "                if max(arr[start:i+1])<=min(arr[i+1:end+1]):  return 1+split(start,i)+split(i+1,end)\n",
    "            return count\n",
    "\n",
    "        return split(0,len(arr)-1)+1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check_merge(self, group_lst: List[int]):\n",
    "        n = len(group_lst)\n",
    "        if len(group_lst) > 1:\n",
    "            for i in range(1,len(group_lst)):            \n",
    "                if min(group_lst[i])<max(group_lst[i-1]):\n",
    "                    group_lst[i-1].extend(group_lst[i])\n",
    "                    del group_lst[i]\n",
    "                    break\n",
    "        else:\n",
    "            return\n",
    "        after = len(group_lst)\n",
    "        if after==n:\n",
    "            return \n",
    "        else:\n",
    "            self.check_merge(group_lst)\n",
    "           \n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        group_lst =[]\n",
    "        cur_lst = []\n",
    "        for v in arr:\n",
    "            # 如果当前列表为空，就添加，如果不为空，判断g是否比group中存在的最后一个列表大\n",
    "            if cur_lst == []:\n",
    "                cur_lst.append(v)\n",
    "            else:\n",
    "              \n",
    "                # 此时构建第一个分组，所有分组列表为空\n",
    "                if v>=max(cur_lst):\n",
    "                    # 比当前的分组列表大，不需要添加进去，第一个分组添加进去\n",
    "                    group_lst.append(cur_lst.copy())\n",
    "                    cur_lst.clear()\n",
    "                    cur_lst.append(v)\n",
    "                else:\n",
    "                    cur_lst.append(v)             \n",
    "        # 比当前的分组列表大，并且比前一个分组的最大还小，不需要添加进去，第一个分组添加进去\n",
    "        group_lst.append(cur_lst.copy())\n",
    "        self.check_merge(group_lst)      \n",
    "        return len(group_lst)\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stk = []\n",
    "        for v in arr:\n",
    "            if not stk or v>=stk[-1]:\n",
    "                stk.append(v)\n",
    "            else:\n",
    "                mp = stk.pop()\n",
    "                while stk and stk[-1]>v:\n",
    "                    stk.pop()\n",
    "                stk.append(mp)\n",
    "        return len(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        points = []\n",
    "        for i in arr:\n",
    "            if not points or i >= points[-1]:\n",
    "                points.append(i)\n",
    "            else:\n",
    "                _max = points.pop()\n",
    "                while points and i < points[-1]:\n",
    "                    points.pop()\n",
    "                points.append(_max)\n",
    "        return len(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        A = accumulate([-inf]+arr[:-1],max)\n",
    "        B = list(accumulate(arr[::-1],min))[::-1]\n",
    "        return sum(a<=b for a,b in zip(A,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def combine_dict_and_sort(idx_dict):\n",
    "    result = []\n",
    "    for key in idx_dict.keys():\n",
    "        result.extend(sorted(idx_dict[key]))\n",
    "    return result    \n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        sorted_arr = sorted(arr)\n",
    "        index_to_num_dict = {}\n",
    "        need_new_key = True\n",
    "        for i in range(len(arr)):\n",
    "            if sorted_arr[:i + 1] != combine_dict_and_sort(index_to_num_dict) + [arr[i]]:\n",
    "                if not need_new_key:\n",
    "                    index_to_num_dict[i] = index_to_num_dict[i - 1] + [arr[i]]\n",
    "                    index_to_num_dict.pop(i - 1)\n",
    "                else:\n",
    "                    index_to_num_dict[i] = [arr[i]]\n",
    "                    need_new_key = False\n",
    "                if sorted_arr[:i + 1] == combine_dict_and_sort(index_to_num_dict):\n",
    "                    need_new_key = True\n",
    "            else:\n",
    "                index_to_num_dict[i] = [arr[i]]\n",
    "                need_new_key = True\n",
    "        return len(index_to_num_dict.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList  \n",
    "        arr_sort = sorted(arr)\n",
    "        cnt = 0\n",
    "\n",
    "        m1 = SortedList([])\n",
    "        m2 = SortedList([])\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            m1.add(x)\n",
    "            m2.add(arr_sort[i])\n",
    "            if m1 == m2:\n",
    "                cnt += 1\n",
    "                m1 = SortedList([])\n",
    "                m2 = SortedList([])\n",
    "\n",
    "        return cnt   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # 每个块的最大值必须是非严格递增的\n",
    "        # 单调栈记录每个块的最大值\n",
    "        stack = []\n",
    "        for i in range(len(arr)):\n",
    "            if len(stack) == 0 or arr[i] >= arr[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                tmp = stack.pop()\n",
    "                while len(stack) > 0 and arr[i] < arr[stack[-1]]:\n",
    "                    stack.pop()\n",
    "                stack.append(tmp)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: [int]) -> int:\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if stack and num < stack[-1]: \n",
    "                head = stack.pop()\n",
    "                while stack and num < stack[-1]: stack.pop()\n",
    "                stack.append(head)\n",
    "            else: stack.append(num)\n",
    "        return len(stack)\n",
    "\n",
    "# 作者：Krahets\n",
    "# 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        st = []\n",
    "        for x in arr:\n",
    "            if st and st[-1]>x:\n",
    "                head = st.pop()\n",
    "                while st and st[-1]>x: st.pop()\n",
    "                st.append(head)\n",
    "            else:\n",
    "                st.append(x)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        \n",
    "        [ max] [min ] \n",
    "        \n",
    "        i\n",
    "        max_l[i]  min_r[i+1]\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        min_r = [0]*n\n",
    "        max_l = [0]*n\n",
    "\n",
    "        min_r[n-1], max_l[0] =  arr[n-1], arr[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            max_l[i] = max(max_l[i-1], arr[i])\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            min_r[i] = min(min_r[i+1], arr[i])\n",
    "        \n",
    "        # print(max_l)\n",
    "        # print(min_r)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(0, n-1):\n",
    "            if max_l[i] <= min_r[i+1]:\n",
    "                # print(i, arr[i], max_l[i], min_r[i+1])\n",
    "                res += 1\n",
    "    \n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxChunksToSorted(self, arr):\n",
    "    \"\"\"\n",
    "    :type arr: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    end, nChunks = 0, 0\n",
    "\n",
    "    while end < len( arr ):\n",
    "      i = end\n",
    "      end = arr[ end ] + 1\n",
    "\n",
    "      while i < end:\n",
    "        while i < end and arr[ i ] < end:\n",
    "          i += 1\n",
    "        if i < end:  # arr[ i ] >= end:\n",
    "          end = arr[ i ] + 1\n",
    "\n",
    "      nChunks += 1\n",
    "\n",
    "    return nChunks\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        j, minv, maxv = 0, n, -1\n",
    "        for i in range(n):\n",
    "            minv, maxv = min(minv, arr[i]), max(maxv, arr[i])\n",
    "            if j == minv and i == maxv:\n",
    "                ans += 1\n",
    "                j = i+1\n",
    "                minv, maxv = n, -1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "    2023-10-10\n",
    "\n",
    "    分析 [4 3 2 1 0]\n",
    "    1. [4] 能不能组合? --> 不能, 4 为最大值, 和后面无法组成有序序列\n",
    "    2. [4 3] 能不能组合? --> 不能, 4 3 排序后为 34, 后面的数值存在比 4 小的数字, 因此无法续上\n",
    "    3. [4 3 2] 能不能组合 --> 不能, 排序后为 2 3 4, 后面存在比 4 小的数字\n",
    "    ...\n",
    "\n",
    "    分析 [1 0 2 3 4]\n",
    "    1. [1] 不能组合, 因为后面存在比 1 小的数字\n",
    "    2. [1 0] 可以组合, 排序后为 [0 1], 后面的数字全部比 1 大\n",
    "    3. [2] 可以组合, 后面的数字全部比 2 大\n",
    "    ...\n",
    "\n",
    "    判断当前区间组合是否可行, 需要比较后面的数字是否全部大于当前区间中的最大值, 即右侧区间的最小值是否大于当前区间的最大值\n",
    "\n",
    "    从右至左构造单调栈, 栈顶为最大值, 例如 \"0 50 100]\" (右侧为栈底)\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [0] * n  ## dp[i] 表示右侧区间 [i, n) 上的最小值\n",
    "        dp[-1] = arr[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp[i] = min(dp[i+1], arr[i])\n",
    "\n",
    "        count = 0\n",
    "        idx = 0\n",
    "        cur_range = [arr[0]]\n",
    "        cur_range_max = arr[0]\n",
    "        cur = arr[0]\n",
    "        idx = 1\n",
    "        while idx < n:\n",
    "            if cur_range_max < dp[idx]:  ## 在 idx 处切割, 即 (x, idx-1] 称为一个组合\n",
    "            # if cur < dp[idx]:  ## 在 idx 处切割, 即 (x, idx-1] 称为一个组合\n",
    "                count += 1\n",
    "                cur_range = [arr[idx]]  ## 从 idx 开始形成新的区间\n",
    "                cur_range_max = arr[idx]\n",
    "            else:\n",
    "                cur_range.append(arr[idx])  ## 不能切割\n",
    "                cur_range_max = max(cur_range_max, arr[idx])\n",
    "            idx += 1\n",
    "        count += 1\n",
    "        return count\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        maxCnt = len(arr) - 1\n",
    "        for i in range(maxCnt):\n",
    "            if max(arr[:i+1]) > min(arr[i+1:]):\n",
    "                maxCnt-=1\n",
    "        return maxCnt + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        s1, s2, ans = set(), set(), 0\n",
    "        for i, num in enumerate(arr):\n",
    "            s1.add(i)\n",
    "            s2.add(num)\n",
    "            if s1 == s2:\n",
    "                ans += 1\n",
    "                s1, s2 = set(), set()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = -1\n",
    "        for i, num in enumerate(arr):\n",
    "            mx = max(mx, num)\n",
    "            if mx == i:\n",
    "                ans += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        start = 0\n",
    "        while i < n:\n",
    "            if max(arr[start:i+1]) == i and min(arr[start:i+1]) == start:\n",
    "                ans += 1\n",
    "                start = i+1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans, mx = 0, 0\n",
    "        for i, num in enumerate(arr):\n",
    "            mx = max(mx, num)\n",
    "            ans += mx == i\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        chunks = 0  # 块的数量\n",
    "        max_value = 0  # 当前块的最大值\n",
    "        for index, value in enumerate(arr):\n",
    "            max_value = max(max_value, value)  # 更新最大值\n",
    "            if index == max_value:\n",
    "                chunks += 1  # 当前索引等于最大值，说明构成了一个块\n",
    "        return chunks\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        st = []\n",
    "        for x in arr:\n",
    "            if not st or x >= st[-1]:\n",
    "                st.append(x)\n",
    "            else:\n",
    "                mx = st.pop()\n",
    "                while st and st[-1] > x:\n",
    "                    st.pop()\n",
    "                st.append(mx)\n",
    "        return len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = 0\n",
    "        for i, e in enumerate(arr):\n",
    "            mx = max(mx, e)\n",
    "            ans += (mx == i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        d0, d1 = Counter(), Counter()\n",
    "        l = len(arr)\n",
    "        arr1 = [i for i in range(l)]\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            d0[arr[i]] += 1\n",
    "            d1[arr1[i]] += 1\n",
    "            if d1 == d0:\n",
    "                ans += 1\n",
    "                d1.clear()\n",
    "                d0.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        mapp = collections.defaultdict(set)\n",
    "        for i, j in enumerate(arr):\n",
    "            mapp[i].add(j)\n",
    "            mapp[j].add(i)\n",
    "        i, front, part = -1, -1, 0\n",
    "        while i < len(arr):\n",
    "            i += 1\n",
    "            for j in mapp[i]:\n",
    "                front = max(front, j)\n",
    "            if i == front:\n",
    "                part += 1\n",
    "        return part\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        #记录当前最大数,是否与数组号相对应\n",
    "        MAX=0;count=0\n",
    "        for i in range(len(arr)):\n",
    "            MAX=max(MAX,arr[i])\n",
    "            if MAX==i:\n",
    "                count+=1\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = ma =0\n",
    "        for i,a in enumerate(arr):\n",
    "            ma = max(ma,a)\n",
    "            ans += (ma == i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        min_index=0\n",
    "        count=0\n",
    "        \n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            min_index=max(min_index,arr[i])\n",
    "            if min_index==i:\n",
    "                count+=1\n",
    "        \n",
    "        return count\n",
    "        \n",
    "        \n",
    "        \n",
    "#         res=[]\n",
    "#         self.dfs(arr,0,[],res)\n",
    "#         print(res)\n",
    "#         if len(res)==0:\n",
    "#             return 1\n",
    "#         return max([len(x) for x in res])\n",
    "    \n",
    "#     def dfs(self,arr,start,path,res):\n",
    "#         if start==len(arr):\n",
    "#             flat=[item for sublist in path for item in sublist]\n",
    "#             if flat==sorted(arr):\n",
    "#                 res.append(list(path))\n",
    "        \n",
    "#         for i in range(start+1,len(arr)+1):\n",
    "#             path.append(sorted(arr[start:i]))\n",
    "#             self.dfs(arr,i,path,res)\n",
    "#             path.pop()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mn = float('inf')\n",
    "        i = n - 1\n",
    "        ans = 0 \n",
    "        while i >= 0:\n",
    "            mn = min(mn, arr[i]) \n",
    "            if mn == i:\n",
    "                ans += 1\n",
    "            i-=1 \n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # 每个元素都不相同 并且范围连续\n",
    "        ans = 0\n",
    "        n = len(arr)\n",
    "        count = {}\n",
    "        for i in range(n):\n",
    "            count[i] = count.get(i, 0) + 1\n",
    "            count[arr[i]] = count.get(arr[i], 0) - 1\n",
    "            if not count[i]:\n",
    "                del count[i]\n",
    "            if i != arr[i] and not count[arr[i]]:\n",
    "                del count[arr[i]]\n",
    "            if not count:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "\n",
    "        t=sorted(arr)\n",
    "        n=len(arr)\n",
    "        mx=-inf\n",
    "        res=0\n",
    "        for a,b in zip(arr,t):\n",
    "            mx=max(mx,a)\n",
    "            if mx==b:\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n, ans = len(arr), 0\n",
    "        j, minv, maxv = 0, n, -1\n",
    "        for i in range(n):\n",
    "            minv, maxv = min(minv, arr[i]), max(maxv, arr[i])\n",
    "            if j == minv and i == maxv:\n",
    "                ans, j, minv, maxv = ans + 1, i + 1, n, -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        tracker = []\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            tracker.append([min(i, arr[i]), max(i, arr[i])])\n",
    "        \n",
    "        #tracker = sorted(tracker, key = lambda x: [x[0], -x[1]])\n",
    "        #print(tracker)\n",
    "        res = 1\n",
    "        prevs = tracker[0][0]\n",
    "        preve = tracker[0][1]\n",
    "        for i in range(1, len(tracker)):\n",
    "            if tracker[i][0] > preve:\n",
    "                res += 1\n",
    "                prevs = tracker[i][0]\n",
    "                preve = tracker[i][1]\n",
    "            preve = max(tracker[i][1], preve)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stk = []\n",
    "        for v in arr:\n",
    "            if not stk or v >= stk[-1]:\n",
    "                stk.append(v)\n",
    "            else:\n",
    "                mx = stk.pop()\n",
    "                while stk and stk[-1] > v:\n",
    "                    stk.pop()\n",
    "                stk.append(mx)\n",
    "        return len(stk)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        chunks = 0  # 块的数量\n",
    "        max_value = 0  # 当前块的最大值\n",
    "        for index, value in enumerate(arr):\n",
    "            max_value = max(max_value, value)  # 更新最大值\n",
    "            if index == max_value:\n",
    "                chunks += 1  # 当前索引等于最大值，说明构成了一个块\n",
    "        return chunks\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ind=collections.Counter()\n",
    "        for i,v in enumerate(arr):\n",
    "            ind[v]=i \n",
    "        arr.sort()\n",
    "        cnt=0\n",
    "        r=-1\n",
    "        for i,v in enumerate(arr):\n",
    "            if i>r:\n",
    "                cnt+=1\n",
    "                r=ind[v]\n",
    "            else:\n",
    "                if ind[v]>r:\n",
    "                    r=ind[v]\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i =0\n",
    "        ans = 0\n",
    "        tmp =-1\n",
    "        while i<n:\n",
    "            if arr[i]!=i:# 这个数字没有出现在应该出现的位置\n",
    "                tmp = max(tmp,arr[i])\n",
    "                if tmp==i:\n",
    "                    ans +=1\n",
    "            else:\n",
    "                if i>=tmp:# 没有到想要到达的位置\n",
    "                    ans +=1\n",
    "            # 第一个块\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=769 lang=python\n",
    "#\n",
    "# [769] 最多能完成排序的块\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def maxChunksToSorted(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        right = 0\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == i and len(stack) == 0:\n",
    "                ans += 1\n",
    "            else:\n",
    "                if arr[i] != i:\n",
    "                    if arr[i] not in stack:\n",
    "                        stack.append(arr[i])\n",
    "                    else:\n",
    "                        stack.remove(arr[i])\n",
    "                    \n",
    "                    if i not in stack:\n",
    "                        stack.append(i)\n",
    "                    else:\n",
    "                        stack.remove(i)\n",
    "                        if len(stack) == 0:\n",
    "                            ans += 1\n",
    "        return ans \n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans=[]\n",
    "        s=set()\n",
    "        temp=[]\n",
    "        for i in range(0,len(arr)):\n",
    "            s.add(i)\n",
    "            temp.append(arr[i])\n",
    "            if set(temp)==s:\n",
    "                ans.append(temp)\n",
    "                temp.clear()\n",
    "                s.clear()\n",
    "\n",
    "        return len(ans)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        i, res, n = 0, 0, len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] == i:\n",
    "                i += 1\n",
    "                res += 1\n",
    "                continue\n",
    "            j, Max, Min = i, arr[i], arr[i]\n",
    "            while j < n and (Min != i or Max - Min + 1 != j - i):\n",
    "                Min = min(Min, arr[j])\n",
    "                Max = max(Max, arr[j])\n",
    "                j += 1\n",
    "            res += 1\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        tracker = []\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            tracker.append([min(i, arr[i]), max(i, arr[i])])\n",
    "        \n",
    "        tracker = sorted(tracker, key = lambda x: [x[0], -x[1]])\n",
    "        print(tracker)\n",
    "        res = 1\n",
    "        prevs = tracker[0][0]\n",
    "        preve = tracker[0][1]\n",
    "        for i in range(1, len(tracker)):\n",
    "            if tracker[i][0] > preve:\n",
    "                res += 1\n",
    "                prevs = tracker[i][0]\n",
    "                preve = tracker[i][1]\n",
    "            preve = max(tracker[i][1], preve)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\r\n",
    "        ans = mx = 0\r\n",
    "        for i, x in enumerate(arr):\r\n",
    "            mx = max(mx, x)\r\n",
    "            ans += mx == i\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack=[]\n",
    "        for num in arr:\n",
    "            if not stack or num >= stack[-1]:\n",
    "                stack.append(num)\n",
    "            else:\n",
    "                mx=stack.pop()\n",
    "                while stack and stack[-1]>num :\n",
    "                    stack.pop()\n",
    "                stack.append(mx)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # stk = []\n",
    "        # for v in arr:\n",
    "        #     if not stk or v >= stk[-1]:\n",
    "        #         stk.append(v)\n",
    "        #     else:\n",
    "        #         mx = stk.pop()\n",
    "        #         while stk and stk[-1] > v:\n",
    "        #             stk.pop()\n",
    "        #         stk.append(mx)\n",
    "\n",
    "        # return len(stk)\n",
    "        size = len(arr)\n",
    "        stack = []\n",
    "        for i in range(size):\n",
    "            m = arr[i]\n",
    "            while stack and arr[i] < stack[-1]:\n",
    "                m = max(stack.pop(), m)\n",
    "            stack.append(m)\n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        count = []\n",
    "        for i in arr:\n",
    "            if not count or i>count[-1]:\n",
    "                count.append(i)\n",
    "            else:\n",
    "                max = count.pop()\n",
    "                while count and i<count[-1]:\n",
    "                    count.pop()\n",
    "                count.append(max)\n",
    "        return len(count)\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: list[int]) -> int:\n",
    "        i_max = 0\n",
    "        result = 0\n",
    "        # n = len(arr)\n",
    "        # for i in range(arr):\n",
    "        #     x = arr[i]\n",
    "        #     if x == a_max:\n",
    "        #         result += 1\n",
    "        for i, x in enumerate(arr):\n",
    "            i_max = max(i_max, x)\n",
    "            if i == i_max:\n",
    "                result += 1\n",
    "                # i_max = 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # if len(arr) == 1:\n",
    "        #     return 1\n",
    "        n = len(arr)\n",
    "        chunk = 1\n",
    "        i, j = 0, 0\n",
    "        max_ = arr[i]\n",
    "        while j < n:\n",
    "            max_ = max(max_, arr[j])\n",
    "            if max_ == j and j != n - 1:\n",
    "                chunk += 1\n",
    "                i = j\n",
    "                if i < n:\n",
    "                    max_ = arr[i]\n",
    "                else: return chunk\n",
    "            j += 1\n",
    "        return chunk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        orgin_d, sorted_d = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for i, j in zip(arr, range(len(arr))):\n",
    "            orgin_d[i] = orgin_d[i] + 1\n",
    "            sorted_d[j] = sorted_d[j] + 1\n",
    "            if orgin_d == sorted_d:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        s=0\n",
    "        p=0\n",
    "        for i in range(len(arr)):\n",
    "            p=max(p,arr[i])\n",
    "            if p==i:\n",
    "                s+=1 \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # stk = []\n",
    "        # for v in arr:\n",
    "        #     if not stk or v >= stk[-1]:\n",
    "        #         stk.append(v)\n",
    "        #     else:\n",
    "        #         mx = stk.pop()\n",
    "        #         while stk and stk[-1] > v:\n",
    "        #             stk.pop()\n",
    "        #         stk.append(mx)\n",
    "\n",
    "        # return len(stk)\n",
    "        size = len(arr)\n",
    "        stack = []\n",
    "        for i in range(size):\n",
    "            m = arr[i]\n",
    "            while stack and arr[i] < stack[-1]:\n",
    "                m = max(stack.pop(), m)\n",
    "            stack.append(m)\n",
    "        \n",
    "        return len(stack)\n",
    "\n",
    "\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        mx = 0\n",
    "        for idx, val in enumerate(arr):\n",
    "            mx = max(mx, val)\n",
    "            res += mx == idx \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        s1, s2, ans = set(), set(), 0\n",
    "        for i, num in enumerate(arr):\n",
    "            s1.add(i)\n",
    "            s2.add(num)\n",
    "            if s1 == s2:\n",
    "                ans += 1\n",
    "                s1, s2 = set(), set()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for i,a in enumerate(arr):\n",
    "            st.append(a)\n",
    "            while(st and i >= st[-1]):\n",
    "                st.pop()\n",
    "            if(st == []): \n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ret = 0\n",
    "        right = arr[0]\n",
    "        for i in range(len(arr)):\n",
    "            right = max(arr[i], right)\n",
    "            if right == i:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            f[i] = x\n",
    "        count, end = 0, 0\n",
    "        for i in range(n):\n",
    "            end = max(end, f[i])\n",
    "            if i == end:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if not stack or arr[i] >= stack[-1]:\n",
    "                stack.append(arr[i])\n",
    "            else:\n",
    "                block_max = stack.pop()\n",
    "                while stack and stack[-1] > arr[i]:\n",
    "                    stack.pop()\n",
    "                stack.append(block_max)\n",
    "        return len(stack)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        mx = ans = 0\n",
    "        for i, v in enumerate(arr):\n",
    "            mx = max(mx, v)\n",
    "            if i == mx:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        mx = ans = 0\n",
    "        for i, v in enumerate(arr):\n",
    "            mx = max(mx, v)\n",
    "            if i == mx:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n, ans = len(arr), 0\n",
    "        left = 0\n",
    "        min_value, max_value = n, -1\n",
    "        for right in range(n):\n",
    "            min_value = min(min_value, arr[right])\n",
    "            max_value = max(max_value, arr[right])\n",
    "            if left == min_value and right == max_value:\n",
    "                ans += 1\n",
    "                left = right + 1\n",
    "                min_value = n\n",
    "                max_value = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack = []\n",
    "        for a in arr:\n",
    "            if len(stack) == 0 or a >= stack[-1]:\n",
    "                stack.append(a)\n",
    "            else:\n",
    "                mx = stack.pop()\n",
    "                while stack and stack[-1] > a:\n",
    "                    stack.pop()\n",
    "                stack.append(mx)\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            mx = max(mx, x)\n",
    "            if i == mx:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        stack=[]\n",
    "        for v in arr:\n",
    "            if not stack or v>=stack[-1]:\n",
    "                stack.append(v)\n",
    "            else:\n",
    "                mx=stack.pop()\n",
    "                while stack and stack[-1]>v:\n",
    "                    stack.pop()\n",
    "                stack.append(mx)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans, stack = 0, []\n",
    "        for i in range(len(arr)):\n",
    "            while stack and stack[-1] < i:\n",
    "                stack.pop()\n",
    "            ans += 1 if not stack else 0\n",
    "            stack.append(arr[i])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: list[int]) -> int:\n",
    "        i_max = 0\n",
    "        result = 0\n",
    "        # n = len(arr)\n",
    "        # for i in range(arr):\n",
    "        #     x = arr[i]\n",
    "        #     if x == a_max:\n",
    "        #         result += 1\n",
    "        for i, x in enumerate(arr):\n",
    "            i_max = max(i_max, x)\n",
    "            if i == i_max:\n",
    "                result += 1\n",
    "                i_max = 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        l=sorted(arr)\n",
    "        e=dict()\n",
    "        re=dict()\n",
    "        for i,a in enumerate(l):\n",
    "            e[i]=a\n",
    "            re[a]=i\n",
    "        n=len(arr)\n",
    "        i=0\n",
    "        last=0\n",
    "        c=0\n",
    "        while i<n:\n",
    "            while i<=last:\n",
    "                #now=arr[i]\n",
    "                last=max(last,arr[i])\n",
    "                i+=1\n",
    "            last+=1\n",
    "            c+=1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans=[]\n",
    "        s=set()\n",
    "        temp=[]\n",
    "        for i in range(0,len(arr)):\n",
    "            s.add(i)\n",
    "            temp.append(arr[i])\n",
    "            if set(temp)==s:\n",
    "                ans.append(temp)\n",
    "                temp.clear()\n",
    "                s.clear()\n",
    "            else:\n",
    "                continue\n",
    "        print(ans)\n",
    "        return len(ans)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        statck = []\n",
    "        for a in arr:\n",
    "            if statck and a < statck[-1]:\n",
    "                head = statck.pop()\n",
    "                while statck and a < statck[-1]: statck.pop()\n",
    "                statck.append(head)\n",
    "            else:\n",
    "                statck.append(a)\n",
    "        return len(statck)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        r = arr[0]\n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            r = max(r, arr[i])\n",
    "            if r == i:\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i =0\n",
    "        ans = 0\n",
    "        tmp =-1\n",
    "        while i<n:\n",
    "            if arr[i]!=i:# 这个数字没有出现在应该出现的位置\n",
    "                tmp = max(tmp,arr[i])\n",
    "                if tmp==i:\n",
    "                    ans +=1\n",
    "                    tmp = -1\n",
    "            else:\n",
    "                if i>=tmp:# 没有到想要到达的位置\n",
    "                    ans +=1\n",
    "            # 第一个块\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\r\n",
    "        mx, cnt = 0, 0\r\n",
    "        for i, v in enumerate(arr):\r\n",
    "            mx = max(mx, v)\r\n",
    "            if mx == i:\r\n",
    "                cnt += 1\r\n",
    "        return cnt\r\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        orgin_d, sorted_d = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        res = 0\n",
    "        for i, j in zip(arr, sorted(arr)):\n",
    "            orgin_d[i] = orgin_d[i] + 1\n",
    "            sorted_d[j] = sorted_d[j] + 1\n",
    "            if orgin_d == sorted_d:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\r\n",
    "        cnt=0\r\n",
    "        idx=0\r\n",
    "        L=len(arr)\r\n",
    "        start=0\r\n",
    "        while idx<L:\r\n",
    "            cnt+=1\r\n",
    "            if arr[idx]==start:\r\n",
    "                # cnt+=1\r\n",
    "                idx+=1\r\n",
    "                start+=1\r\n",
    "                continue\r\n",
    "            l=r=arr[idx]\r\n",
    "            offset=1\r\n",
    "            while True:\r\n",
    "                l=min(arr[idx+offset],l)\r\n",
    "                r=max(arr[idx+offset],r)\r\n",
    "                if l==start and r==l+offset:\r\n",
    "                    break\r\n",
    "                offset+=1\r\n",
    "            start=r+1\r\n",
    "            idx+=offset+1\r\n",
    "        return cnt\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        max_block = 0\n",
    "        max_num = -1\n",
    "        for i, num in enumerate(arr):\n",
    "            max_num = max(max_num, num)\n",
    "            if i == max_num:\n",
    "                max_block += 1\n",
    "        return max_block"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # ans = 1\n",
    "        # stack = []\n",
    "        # for i in range(n):\n",
    "        #     while stack and arr[stack[-1]] < arr[i]:\n",
    "        #         top = stack.pop()\n",
    "        #         if not stack:\n",
    "        #             ans += 1\n",
    "        #     stack.append(i)\n",
    "        # return ans\n",
    "        ans = 0\n",
    "        Sum = 0\n",
    "        Sid = 0\n",
    "        for i,v in enumerate(arr):\n",
    "            Sum += v\n",
    "            Sid += i\n",
    "            if Sum == Sid:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            mx = max(mx, x)\n",
    "            ans += mx == i\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            if max(arr[:i + 1]) == i:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        mx = ans = 0\n",
    "        for i,x in enumerate(arr):\n",
    "            mx =max(mx,x)\n",
    "            if mx==i:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        # if len(arr) == 1:\n",
    "        #     return 1\n",
    "        n = len(arr)\n",
    "        chunk = 1\n",
    "        i, j = 0, 0\n",
    "        max_ = arr[i]\n",
    "        while j < n:\n",
    "            max_ = max(max_, arr[j])\n",
    "            if max_ == j and j != n - 1:\n",
    "                chunk += 1\n",
    "                j += 1\n",
    "                i = j\n",
    "                if i < n:\n",
    "                    max_ = arr[i]\n",
    "                else: return chunk\n",
    "            else:\n",
    "                j += 1\n",
    "        return chunk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxChunksToSorted(self, arr: List[int]) -> int:\n",
    "        count = 0\n",
    "        max_seen = -1\n",
    "        for i, num in enumerate(arr):\n",
    "            max_seen = max(max_seen, num)\n",
    "            if max_seen == i:\n",
    "                count += 1\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
